// 多数元素
// 方法 1 hash set
var countNums = function (nums) {
  let counts = new Map()
  for (let num of nums) {
    if (!counts.has(num)) {
      counts.set(num, 1)
    } else {
      counts.set(num, counts.get(num) + 1)
    }
  }
  return counts
}
var majorityElement = function (nums) {
  let counts = countNums(nums)
  let max = null
  let ans = null
  for (let [key, value] of counts) {
    if (max === null || value > max) {
      max = value
      ans = key
    }
  }
  return ans
}
// 方法 2 排序 右移整除
var majorityElement = function (nums) {
  nums.sort()
  return nums[nums.length >> 1]
}
// 方法 3 随机化 这个数出现的次数要大于 nums.length >> 1 就是众数
// 时间复杂度 O(N) 空间复杂度 O(1)
let isMax = function (nums, num) {
  let count = 0
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === num) {
      count++
    }
  }
  return count
}
var majorityElement = function (nums) {
  let n = nums.length >> 1
  while (true) {
    let v = nums[Math.floor(Math.random() * nums.length)]
    if (isMax(nums, v) > n) {
      return v
    }
  }
}
// 方法 4 分治
var countInRange = function (nums, val, l, r) {
  let count = 0
  for (let i = l; i <= r; i++) {
    if (val === nums[i]) count++
  }
  return count
}
var dfs = function (nums, l, r) {
  if (l === r) {
    return nums[l]
  }
  let mid = l + ((r - l) >> 1)
  let left = dfs(nums, l, mid)
  let right = dfs(nums, mid + 1, r)

  if (left === right) return left
  let leftCount = countInRange(nums, left, l, r)
  let rightCount = countInRange(nums, right, l, r)
  return leftCount > rightCount ? left : right
}
var majorityElement = function (nums) {
  return dfs(nums, 0, nums.length - 1)
}

// 方法 5 投票算法 Boyer-Moore
// count 为 0 说明这段数字的众数和非众数数量相当
// 在数组的后段，重新找
// 因为众数数量 必须大于 所有元素的一半，不能等于一半
// 所以 后段里面一定存在 前段里面的 出现的众数，
// 而且这个数在后段里面也是超过后段数量的一半的
var majorityElement = function (nums) {
  let count = 0
  let ans = null
  for (let num of nums) {
    if (count === 0) {
      ans = num
    }
    count += num === ans ? 1 : -1
  }
  return ans
}

// let r = majorityElement([7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 2, 5, 5, 5])
// console.log(r)
